package Javafoundation;

import java.util.Scanner;
import java.util.StringTokenizer;

public class BinarySortTree {
    private static Node root;
    private Node temp;
    private String str = "";
    private Node left;
    private Node right;


    public static void main(String[] args) throws ElementNotFoundException {
        String st = "10 18 3 8 12 2 7 3";
        StringTokenizer tokenizer = new StringTokenizer(st);
        int[] number = new int[tokenizer.countTokens()];
        int i = 0;
        while(tokenizer.hasMoreTokens()){
            number[i] = Integer.parseInt(tokenizer.nextToken());
            i++;
        }
        BinarySortTree tree = new BinarySortTree();
        for(int m=0;m<number.length;m++){
            tree.add(number[m]);
        }
        tree.print();
        System.out.println("请输入你想查找的数据： ");
        Scanner scan = new Scanner(System.in);
        int cha = scan.nextInt();
        scan.nextLine();
        Node n=tree.search(root,cha);
        if(n!=null)
            System.out.println("查找到的结果为： "+n.getData());
        else{
            System.out.println("找不到关键字！将关键字插入进去，显示新的二叉排序树：");
            tree.add(cha);
            tree.print();
        }
        System.out.println("请输入你想要插入的左孩子：");
        int cha1 = scan.nextInt();
        tree.add(cha1);
        tree.print();
        System.out.println("请输入你想要插入的右孩子：");
        int cha2 = scan.nextInt();
        tree.add(cha2);
        tree.print();

        System.out.println("请输入你想删除的数字");
        int d = scan.nextInt();
        root = root.remove(root,d);
        tree.print();


    }




    public BinarySortTree() {
        root = null;
    }

    //向二叉树插入元素
    public void add(int data1) {
        if (this.root == null) {
            root = new Node(data1);
            temp = root;//存下第一个节点
        } else {
            addW(root,data1);
        }

    }

    //判定插入元素的位置，在二叉树中进行插入
    public void addW(Node x,int data1) {
        //当数据大于等于节点时，放右子树
        if (data1 >= x.getData()) {
            if (x.getRight() == null) {
                x.setRight(new Node(data1));
            } else {
                addW(x.getRight(),data1);
            }
        }
        //数据小于节点时，放左子树
        else {
            if (x.getLeft() == null) {
                x.setLeft(new Node(data1));
            } else {
                this.addW(x.getLeft(),data1);
            }
        }
    }

    public void print() {
        root.print();
        System.out.println();
    }

    //在二叉树中寻找元素
    public Node search(Node x,int data2) {
        if(x==null)
            return null;
        if(data2==x.getData()){
            return x;
        }
        else if(data2<x.getData()){
            return search(x.getLeft(),data2);
        }
        else {
            return search(x.getRight(),data2);
        }
    }

    public Node getRoot() {
        return root;
    }

}
